class Solution {
public:
    int findDuplicate(vector<int>& nums) {
      int n = nums.size();
      int l = 1,r = n-1 ,mid;
      while(l<r){
        mid = (l+r)/2;
        int cnt = 0;
        for(int i=0;i<n;i++){
          if(nums[i]<=mid){
            cnt++;
          }
        }
        if(cnt>mid){
          r=mid;
        }else{
          l=mid+1;
        }
      }
    return r;
    }
};
